import java.util.ArrayList;
import java.util.List;

public class demo1 {
    boolean[][] ret1;
    boolean[][] ret2;
    int m,n;
    int []dx={0,0,-1,1};
    int []dy={1,-1,0,0};
    //注意细节问题  海洋中水都能灌溉边界
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>>lists=new ArrayList<>();
        m=heights.length;
        n=heights[0].length;
        if(m==0||n==0)return lists;
        ret1=new boolean[m][n];
        ret2=new boolean[m][n];
        for(int i=0;i<m;i++){
            if(!ret1[i][0]){
                dfs(heights,i,0,ret1);
            }
            if(!ret2[i][n-1]){
                dfs(heights,i,n-1,ret2);
            }
        }
        for(int j=0;j<n;j++){
            if(!ret1[0][j]){
                dfs(heights,0,j,ret1);
            }
            if(!ret2[m-1][j]){
                dfs(heights,m-1,j,ret2);
            }
        }
        for(int x=0;x<m;x++){
            for(int y=0;y<n;y++){
                List<Integer>list=new ArrayList<>();
                if(ret1[x][y]&&ret2[x][y]){
                    list.add(x);
                    list.add(y);
                    lists.add(list);
                }

            }

        }
        return lists;
    }
    public void dfs(int[][]heights,int i,int j,boolean[][]ret){
        ret[i][j]=true;
        for(int k=0;k<4;k++){
            int a=i+dx[k];
            int b=j+dy[k];
            if(a>=0&&a<m&&b>=0&&b<n&&!ret[a][b]&&heights[a][b]>=
                    heights[i][j]){
                dfs(heights,a,b,ret);
            }
        }
    }
}
